/*
 * @lc app=leetcode.cn id=496 lang=typescript
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const hash: Map<number, number> = new Map();
  const stack = [];
  // 计算num2中所有元素的下一个更大元素，放入hash中保存
  for (const num of nums2) {
    while (stack.length && num > stack[stack.length - 1]) {
      hash.set(stack[stack.length - 1], num);
      stack.pop();
    }
    stack.push(num);
  }

  const ans = [];
  // 从hash中得到下一个更大元素
  for (const num of nums1) {
    ans.push(hash.get(num) || -1);
  }

  return ans;
}
// @lc code=end
